package com.it.myh.test;

import java.awt.geom.Point2D;
import java.util.ArrayList;
import java.util.Collections;
import java.util.List;

public class ConvexHullMaxArea {
    public static void main(String[] args) {
        int k = 5;  // 选取的假位置数量
        List<Point2D.Double> arr = new ArrayList();
        arr.add(new Point2D.Double(39.954706,116.423098));
        arr.add(new Point2D.Double(40.013864,116.306525));
        arr.add(new Point2D.Double(39.954672,116.422953));
        arr.add(new Point2D.Double(39.998968,116.338481));
        arr.add(new Point2D.Double(40.011557,116.321238));
        arr.add(new Point2D.Double(39.954772,116.42305));
        List<Point2D.Double> convexHull = calculateConvexHull(arr);  // 计算所有假位置的凸包
        List<Point2D.Double> selectedFakeLocations = getLargestConvexHull(convexHull, k);  // 选取凸包面积最大的k个假位置

        System.out.println("Selected fake locations:");
        for (Point2D.Double location : selectedFakeLocations) {
            System.out.println("(" + location.x + ", " + location.y + ")");
        }
        Double doubles = calculateConvexHullArea(selectedFakeLocations);
        System.out.println(doubles);
    }

    // 计算凸包
    public static List<Point2D.Double> calculateConvexHull(List<Point2D.Double> points) {
        List<Point2D.Double> sortedPoints = new ArrayList<>(points);
        Collections.sort(sortedPoints, (a, b) -> Double.compare(a.x, b.x));  // 按照x坐标进行排序

        List<Point2D.Double> upperHull = new ArrayList<>();
        for (Point2D.Double point : sortedPoints) {
            while (upperHull.size() >= 2 && !isRightTurn(upperHull.get(upperHull.size() - 2), upperHull.get(upperHull.size() - 1), point)) {
                upperHull.remove(upperHull.size() - 1);
            }
            upperHull.add(point);
        }

        List<Point2D.Double> lowerHull = new ArrayList<>();
        for (int i = sortedPoints.size() - 1; i >= 0; i--) {
            Point2D.Double point = sortedPoints.get(i);
            while (lowerHull.size() >= 2 && !isRightTurn(lowerHull.get(lowerHull.size() - 2), lowerHull.get(lowerHull.size() - 1), point)) {
                lowerHull.remove(lowerHull.size() - 1);
            }
            lowerHull.add(point);
        }

        lowerHull.remove(0);
        lowerHull.remove(lowerHull.size() - 1);
        upperHull.addAll(lowerHull);

        return upperHull;
    }

    // 判断三个点是否是右转方向
    private static boolean isRightTurn(Point2D.Double a, Point2D.Double b, Point2D.Double c) {
        return (b.x - a.x) * (c.y - a.y) - (b.y - a.y) * (c.x - a.x) < 0;
    }

    // 选取凸包面积最大的k个假位置
    public static List<Point2D.Double> getLargestConvexHull(List<Point2D.Double> convexHull, int k) {
        int n = convexHull.size();
        if (k >= n) {
            return convexHull;  // 如果k大于等于凸包中点的数量，直接返回整个凸包
        } else {
            double maxArea = 0;
            int maxIndex = 0;
            for (int i = 0; i <= n - k; i++) {
                List<Point2D.Double> subHull = convexHull.subList(i, i + k);
                double area = calculateConvexHullArea(subHull);
                if (area > maxArea) {
                    maxArea = area;
                    maxIndex = i;
                }
            }
            return convexHull.subList(maxIndex, maxIndex + k);
        }
    }

    // 计算凸包的面积
    public static double calculateConvexHullArea(List<Point2D.Double> points) {
        double area = 0;
        int n = points.size();
        for (int i = 0; i < n; i++) {
            Point2D.Double current = points.get(i);
            Point2D.Double next = points.get((i + 1) % n);
            area += (current.x * next.y - next.x * current.y);
        }
        return Math.abs(area / 2);
    }
}

